\newpage
\section{Навчання з підсиленням (reinforcement learning)}

\subsection{Короткий вступ}

\emph{Навчання з підсиленням (Reinforcement learning)} - навчання про те, які дії потрібно приймати залежно від ситуації таким чином, щоб максимізувати \emph{числовий сигнал "винагороди" (reward signal)}. "Учневі" не вказується, які дії потрібно приймати, щоб досягти мети, а натомість дається можливість самому вибирати  з певного набору допустимих дій. В результаті багаторазової взаємодії з середовищем шляхом методу спроб та помилок досягається оптимальна ``стратегія''.

В загальному випадку, вибрані дії впливають не тільки на винагороду, що слідує безпосередньо після вчинення дії, але й на майбутні ситуації, що, в свою чергу, дає вплив на мабутні винагороди.

В навчанні з підсиленням присутні дві сутності "--- агент та середовище. Агент "--- це все те, на що ми можимо чинити безпосередній вплив.
Накриклад, якщо ми маємо робота, то агентом може бути як весь робот, якщо ми здатні безпосередньо керувати поворотом коліс. Або агентом можна визначити лише електромотори, які зумовлюють поворот коліс та їх рух. В останньому випадку, ми безпосередньо можемо впливати тільки на силу струму, що подається на електромотори. На самі ж колеса ми впливаємо опосередковано, тому вони вважаються середовищем, по відношенню до нашого агента.

\begin{figure}[!h]\begin{center}
\includegraphics[width=0.7\textwidth]{agent_env_diagram.png}
\caption{Взаємодія агента та середовища в навчанні з підсиленням}
\end{center}\end{figure}

Стан системи "--- набір параметрів, які задають наші знання (можливо неповні) про
оточуючий світ. Це, фактично, наше сприйняття поточної ситуації.
Наприклад, у випадку автономного керування транспортним засобом, станом буде інформація про
відстань до найближчої перешкоди, відстань до заданої цілі, можливо, поточна
швидкість самого транспортного засобу тощо.

Складовими частинами системи навчання з підсиленнями є:
\begin{itemize}
\item \emph{Стратегія (policy)}, яка визначає те, які дії будуть прийматися
залежно від ситуації на даний момент часу. Це фактично є поточний інтелект
системи.
\item \emph{Функція винагороди (reward function)}, яка задає відображення зі стану системи та здійсненої дії у множину дійсних чисел "--- множину винагород. Тобто після кожної здійсненої дії, залежно від стану системи, агент отримує певне миттєве значення винагороди. Глобальною метою агента є максимізація загальної винагороди, отриманої протягом всього часу дії.
\item \emph{Ціннісна функція (value function)}, яка, на відміну від функції
винагороди, задає не те, що є ``корисним'' безпосередньо зараз, а те, що є
корисним в більш глобальному значенні, з урахуванням майбутніх станів.
\end{itemize}

Розглянемо ці поняття більш формально.

\subsection{Модель навчання з підсиленням}

\emph{Агент (agent)} та \emph{середовище (environment)} взаємодіють в кожен дискретний момент часу $t=0,1,2,\dots$. На кожному кроці $t$ агент отримує певне представлення \emph{стану системи (state)} $s_t \in \mathcal{S}$, де $\mathcal{S}$ "--- множина усіх станів системи, і на базі цього вибирає \emph{дію (action)} $a_t \in \mathcal{A}(s_t)$, де $\mathcal{A}(s_t)$ "--- множина допустимих дій у стані $s_t$. На наступному кроці $t+1$, частково як наслідок виконаної дії, агент отримує числову \emph{винагороду (reward)} $r_{t+1} \in \mathbb{R}$ і опиняється в стані $s_{t+1}$.

\begin{figure}[!h]\begin{center}
\includegraphics[width=0.7\textwidth]{agent_env_diagram.png}
\caption{Взаємодія агента та середовища в навчанні з підсиленням.}
\end{center}\end{figure}

В загальному випадку, на кожному кроці агент реалізовує відображення станів системи на ймовірності здійснення можливої дії. Таке відображення називається \emph{стратегією (policy)} агента і позначається $\pi_t$, де $\pi_t(s,a)$ "--- це ймовірність, що $a_t=a$, якщо $s_t = s$. Методи навчання з підсиленням визначають, як саме агент змінює свою стратегію в результаті набутого досвіду. Мета агента, грубо кажучи,"--- максимізувати сукупну винагороду, яку він отримує протягом багатьох ходів.

\subsection{Прибуток (return)}

Визначимо більш точно мету агента. Нехай, починаючи з часу $t$, агент отримує послідовність винагород $r_{t+1}, r_{t+2}, r_{t+3}, \ldots$. Тоді основною метою агента буде максимізація \emph{очікуваного прибутку (expected return)} $R_t$, де $R_t$ "--- це певна функція від послідовності винагород. В найпростішому випадку прибуток є сумою усіх винагород:

\begin{equation}
R_t = r_{t+1} + r_{t+2} + \cdots + r_T,
\end{equation}
де $T$ "--- кінцевий момент часу. Такий підхід до визначення прибутку підходить там, де можна природно визначити фінальний момент часу, тобто в таких системах, в яких взаємодія агента і середовища природньо розбивається на окремі підпослідовності (\emph{епізоди}), наприклад, партії в грі, проходи по лабіринту або будь-який інший вид повторюваних взаємодій.

Кожен епізод закінчується у \emph{кінцевому, термінальному стані (terminal state)}, після якого відбувається встановлення стану системи в певний початковий стан з множини можливих початкових станів і розпочинається наступний епізод. Задачі, в яких взаємодія агента і середовища відбувається у вигляді послідовності епізодів, називаються \emph{епізодичними задачами (episodic tasks)}. В епізодичних задачах інколи розмежовують множину усіх нетермінальних станів системи $\mathcal{S}$ та множину усіх станів, включно з термінальними $\mathcal{S^+}$.

З іншого боку, не завжди можна здійснити природній поділ на епізоди, натомість взаємодія відбуваєть постійно без закінчення. Прикладом такої задачі може бути діяльність робота з великою тривалістю життєдіяльності. Такі задачі назвемо \emph{неперервними задачами (continuing tasks)}. В такому випадку кінцевий момент часу $T=\infty$, а сам прибуток, який ми намагаємося максимізувати може легко прямувати до нескінченості (наприклад, якщо на кожному кроці $r_t=1$). Щоб подолати ці труднощі, введемо дещо інше визначення прибутку.

Розглянемо додаткову концепцію "--- \emph{дисконтування (discounting)}. Згідно з нею, агент намагаєтсья вибирати такі дії, щоб максимізувати суму дисконтованих винагород, які він отримає в майбутньому. Зокрема, агент вибирає таку дію $a_t$, яка максимізує очікуваний \emph{дисконтований прибуток (discounted reward)}:

\begin{equation}
R_t = r_{t+1} + \gamma r_{t+2} + \gamma^2 r_{t+3} + \cdots = \sum_{k=0}^{\infty}\gamma^k r_{t+k+1},
\end{equation}
де $\gamma$ "--- це параметр, який називається \emph{дисконтною ставкою (discount rate)}, $0\leq\gamma\leq 1$.

Дисконтна ставка визначає поточну вагу майбутньої винагороди: винагорода, отримана через $k$ кроків у майбутньому, має вагу лише $\gamma^k$, напротивагу одиничній вазі, яку б вона мала, якби була отримана на поточному кроці. Якщо $\gamma<1$, то ця нескінченна сума має скінченне значення, якщо послідовність $\left\{r_k\right\}$ "--- обмежена. Якщо $\gamma = 0$, то агент є ``недалекоглядним'' і буде дбати лише про максимізацію миттєвої винагороди. Його задачею в такому випадку буде вибір такої дії $a_t$, щоб максимізувати лише винагороду $r_{t+1}$. Якщо дія агента не здійснює вплив на майбутні винагороди, то такий підхід дійсно дасть змогу вивчити оптимальну стратегію, однак в більшості випадків це не так, тому максимізація лише миттєвої нагороди може призвести до того, що буде втрачено нагоду ``заробити'' більше в майбутньому, здійснивши на даному кроці дію, яка принесе не максимальну миттєву винагороду. З наближенням $\gamma$ до 1, агент буде надавати майбутнім винагородам все більшого значення: агент стає більш ``далекоглядним''.

\subsection{Ціннісна функція (value function)}

Практично всі алгоритми навчання з підсиленням базуються на оцінці \emph{ціннісної функції (value function)} "--- функції станів системи (або пари стан-дія), що оцінює \emph{наскільки добре} для агента перебувати в заданому стані (або наскільки добре здійснити задану дію, перебуваючи в заданому стані). Фраза ``наскільки добре'' визначається в термінах майбутніх винагород або, що є точнішим визначенням, в термінах очікуваного майбутнього прибутку. Очевидно, що майбутні винагороди залежать від того, які дії здійснювати, тобто від стратегії, тому ціннісна функція визначається з врахуванням певної стратегії.

Нагадаємо, що стратегія $\pi$ "--- це відображення кожного стану $s \in \mathcal{S}$ та кожної допустимої дії $a \in \mathcal{A}(s)$ на ймовірність $\pi(s,a)$ здійснення дії $a$, будучи в стані $s$. \emph{Цінність} стану $s$ згідно стратегії $\pi$, $V^\pi(s)$,"--- це очікуваний прибуток, який можна отримати, якщо почати зі стану $s$ і діяти згідно стратегії $\pi$:
\begin{equation}
V^\pi(s) = E_\pi \Bigl\{ R_t \Big| s_t = s \Bigr \} = E_\pi \Biggl\{\sum_{k=0}^{\infty}\gamma^k r_{t+k+1} \Bigg| s_t=s \Biggr\},
\end{equation}
де $E_\pi{}$ позначає математичне очікування в випадку, якщо агент діє згідно стратегії $\pi$. Потрібно відмітити, що цінність термінального стану завжди рівна нулю. Назвемо функцію $V^\pi$ \emph{ціннісною функцією станів (state-value function) для статегії $\pi$}.

Аналогічно, визначимо цінність здійснення дії $a$ в стані $s$ згідно стратегії $\pi$, $Q^\pi(s,a)$, як очікуваний прибуток, отриманий в результаті перебування в стані $s$, здійснення дії $a$ та подальшому слідуванні стратегії $\pi$:
\begin{equation}
Q^\pi(s,a)=E_\pi \Bigl\{ R_t \Big| s_t=s, a_t=a \Bigr\} = E_\pi \Biggl\{\sum_{k=0}^{\infty}\gamma^k r_{t+k+1} \Bigg| s_t=s,a_t=a \Biggr\}.
\end{equation}
Назвемо функцію $Q^\pi$ \emph{ціннісною функцією дій (action-value function) для статегії $\pi$}.

Ціннісні функції $V^\pi$ та $Q^\pi$ можуть бути оцінені з досвіду. Наприклад, якщо агент притримується стратегії $\pi$ і підтримує середнє значення всіх прибутків, які були реально отримані, для кожного стану, в яких перебував агент, то середнє значення збіжиться до значення цінності для даного стану $V^\pi(s)$ за умови, що кількість перебувань в кожному зі станів прямує до нескінченності. Якщо зберігати середні значення окремо для кожної пари стан-дія, то таке ж твердження вірне і для функції $Q^\pi$. Такі методи оцінки ціннісних функцій називаються \emph{методами Монте-Карло}, тому що вони використовують усереднення по випадкових прикладах реальних прибутків. Проте, якщо кількість станів та можливих дій велика, це унеможливлює збереження середніх значень для кожного стану (пари стан-дія). В такому випадку можна застосувати інші методи, зокрема такі, що використовують апроксиматори функцій. Ми розглянемо їх дещо пізніше.

Фундаментальна властивість ціннісних функцій, яка використовується в навчанні з підсиленням і динамічному програмуванні,"--- це певне рекурсивне співвідношення, якому задовільняє ціннісна функція. Для будь-якої стратегії $\pi$ та будь-якого стану $s$, наступне співвідношення завжди виконується:
\begin{eqnarray}
V^\pi(s) & = & E_\pi \Bigl\{R_t \Big| s_t = s \Bigr\} \nonumber\\
			& = & E_\pi \Biggl\{\sum_{k=0}^{\infty}\gamma^k r_{t+k+1} \Bigg| s_t = s \Biggr\} \nonumber\\
			& = & \sum_a \pi(s,a)\sum_{s'}\mathcal{P}^a_{ss'} \left[ \mathcal{R}^a_{ss'}+\gamma E_\pi \left\{\sum_{k=0}^{\infty}\gamma^k r_{t+k+2} \Bigg| s_{t+1} = s' \right\} \right] \nonumber\\
			& = & \sum_a \pi(s,a)\sum_{s'}\mathcal{P}^a_{ss'} \left[ \mathcal{R}^a_{ss'}+\gamma V^\pi(s') \right],
\label{Bellman_eq}
\end{eqnarray}
де $\mathcal{P}^a_{ss'}$ "--- це ймовірність переходу (transition probability) зі стану $s$ в стан $s'$ при виконанні дії $a$; $\mathcal{R}^a_{ss'}$ "--- очікувана винагорода, яка дається агенту при переході зі стану $s$ в стан $s'$ при виконанні дії $a$. В даній формулі неявно розуміється, що $s \in \mathcal{S}$, дії $a$ беруться з множини $\mathcal{A}(s)$, а $s' \in \mathcal{S}$ у випадку неперервної задачі або $s' \in \mathcal{S^+}$ "--- у випадку епізодичної задачі.

Рівняння (\ref{Bellman_eq}) називається \emph{рівнянням оптимальності Беллмана для $V^\pi$ (Bellman optimality equation for $V^\pi$)}. Воно відображає зв'язок між цінністю стану $s$ та цінностями станів $s'$, в які можна потрапити з $s$. Функція $V^\pi$ "--- єдиний розв'язок рівняння Беллмана. Відмітимо також, що це рівняння "--- основа для багатьох методів обчислення, наближення та вивчення $V^\pi$.

\subsection{Оптимальні функції цінності}

Розв'язування задачі навчання з підсиленням означає, згрубша, знаходження такої стратегії, яка б давала великий прибуток в довгостроковій перспективі. Спробуємо визначити оптимальність стратегії наступним чином. Ціннісні функції визначають частковий порядок на множині усіх стратегій. Стратегію $\pi$ називатимемо \emph{кращою}, ніж стратегія $\pi '$, якщо її очікуваний прибуток більший або рівний від такого ж для стратегії $\pi '$ для усіх станів $s \in \mathcal{S}$:
\begin{equation}
\pi \geq \pi ' \Leftrightarrow \Bigl(\forall s \in \mathcal{S}\Bigr)\left\{ V^\pi(s) \geq V^{\pi '}(s) \right\}
\end{equation}

Завжди існує хоча б одна така стратегія, яка краща або рівна за всіх інших. Така стратегія називається \emph{оптимальною}. Хоча оптимальних стратегій може бути декілька, всіх їх будемо позначати як $\pi^*$. Усі оптимальні стратегії розділяють одну і ту ж ціннісну функцію станів, яка називається \emph{оптимальною ціннісною функцією станів} $V^*$:
\begin{equation}
V^* = \max_\pi V^\pi(s),\qquad \forall s \in \mathcal{S}.
\end{equation}

Оптимальні стратегії також розділяють одну і ту ж \emph{ціннісну функцію дій} $Q^*$:
\begin{equation}
Q^* = \max_\pi Q^\pi(s,a),\qquad \forall s \in \mathcal{S}, \forall a \in \mathcal{A}(s).
\end{equation}

Ми можемо також записати функцію $Q^*$ в термінах $V^*$:
\begin{equation}
Q^*(s,a) = E\left\{r_{t+1} + \gamma V^*(s_{t+1}) \Big| s_t=s, a_t=a \right\}.
\end{equation}

\subsection{Марківський процес прийняття рішення}
      //-1.0/java.lang.Math.log(2+stepsDone)
      //-1.0 + 0.5*Math.exp(-2.0*curState.goalDistance/width)
      //0.0

\section{Методи розв'язування задач навчання з підсиленням}

Існує три широких класи методів, призначених для розв'язування задач навчання з підсиленням:
\begin{itemize}
\item методи динамічного програмування (dynamic programming methods);
\item методи Монте-Карло (Monte Carlo methods);
\item метод часової різниці (temporal-difference learning).
\end{itemize}

Кожен з цих класів має свої сильні та слабкі сторони. Так, методи динамічного програмування є добре розробленими з математичної точки зору, але потребують повної і достатньо точної моделі середовища, що часто просто неможливо задовільнити. Методи Монте-Карло не потребують моделі середовища і є концептуально простими, проте вони не є пристосованими до покрокових послідовних обчислень. Методи ж навчання з часовою різницею не потребують моделі середовища і добре пристосовані до послідовних покрокових обчислень, але є складнішими для аналізу. Ці методи також відрізняються в плані ефективності та швидкості збіжності.

В даній роботі був використаний саме останній метод, на якому зупинимося більш детально.

\begin{table}
\begin{tabular}{|l|}
\hline\\
Ініціалізація:\\
\hspace{0.5cm} $\pi(s) \leftarrow $ стратегія, яку потрібно вичислити\\
\hspace{0.5cm} $V(s) \leftarrow $ довільна ціннісна функція стану\\
\hspace{0.5cm} $Returns(s) \leftarrow $ порожній список прибутків, для всіх $s \in \mathcal{S}$\\
\\
Повторювати постійно:\\
\hspace{0.5cm} a) здійснити генерацію епізоду, використовуючи стратегію $\pi$\\
\hspace{0.5cm} b) для кожного стану $s$, що був відвіданий протягом останнього епізоду:\\
\hspace{1cm}      $R \leftarrow $ прибуток, отриманий після першого візиту стану\\
\hspace{1cm}      додати $R$ до списку $Returns(s)$\\
\hspace{1cm}      $V(s) \leftarrow $ середнє арифметичне($Returns(s)$)\\
\\
\hline
\end{tabular}
\caption{Метод Монте-Карло першого візиту (first-visit Monte Carlo) для знаходження $V^\pi$.}
\end{table}

\begin{table}
\begin{tabular}{|l|}
\hline\\
Ініціалізація, для всіх $s \in \mathcal{S},\ a \in \mathcal{A}(s)$:\\
\hspace{0.5cm} $Q(s,a) \leftarrow $ довільна ціннісна функція стану-дії\\
\hspace{0.5cm} $\pi \leftarrow $ довільна стратегія\\
\hspace{0.5cm} $Returns(s,a) \leftarrow $ порожній список\\
\\
Повторювати постійно:\\
\hspace{0.5cm} a) здійснити генерацію епізоду, використовуючи стратегію $\pi$\\
\hspace{0.5cm} b) для кожної пари $(s,a)$, що з'являлася в епізоді:\\
\hspace{1cm}      $R \leftarrow $ прибуток, отриманий після першого візиту $(s,a)$\\
\hspace{1cm}      додати $R$ до списку $Returns(s,a)$\\
\hspace{1cm}      $Q(s,a) \leftarrow $ середнє арифметичне($Returns(s,a)$)\\
\hspace{0.5cm} c) для кожного стану $s$, що був відвіданий протягом епізоду:\\
\hspace{1cm}      $\pi(s) \leftarrow $ $\arg\max_aQ(s,a)$\\
\\
\hline
\end{tabular}
\caption{Алгоритм Монте-Карло для обчислення оптимального керування (Monte Carlo ES) для знаходження $Q^\pi$.}
\end{table}

\subsubsection{Soft стратегії}

Для soft стратегій, ймовірність $\pi(s,a)>0,\ \forall \pi, \forall s \in \mathcal{S}, a \in \mathcal{A}(s)$.

Одним з найпростіших випадків soft стратегії є $\varepsilon$-жадібна стратегія. В такій стратегії в основному вибирається дія, яка дає поточний максимум ціннісної функції, проте інколи, з ймовірністю $\varepsilon$ приймається рішення про здійснення довільної випадкової допустимої дії. Таким чином будь-яка не жадібна дія отримує ймовірність виконання, рівну $\frac{\varepsilon}{|\mathcal{A}(s)|}$, а жадібна дія, відповідно, $ 1 - \varepsilon + \frac{\varepsilon}{|\mathcal{A}(s)|}$.

\subsection{Навчання з часовою різницею (TD-методи)}

Ідея методів \emph{навчання з часовою різницею (temporal-difference, TD-навчання)} є, мабуть, центральною та найбільш новаторською для всього навчання з підсиленням. TD-навчання "--- це поєднання ідей методів Монте-Карло та динамічного програмування. TD-методи можуть, як і методи Монте-Карло, навчатися лише з досвіду, не потребуючи знання моделі динаміки середовища. З іншого боку, так само як і в методах динамічного програмування, TD-методи оновлюють свої оцінки частково на основі інших оцінок, не чекаючи закінчення епізоду (вони здійснюють bootstrap).

\subsubsection{TD-прогнозування}

Як TD, так і Монте-Карло методи використовують отриманий досвід для розв'язування задачі прогнозування. Маючи певний досвід, отриманий в результаті притримування стратегії $\pi$, обидва методи використовують його для оновлення наближення $V$ до $V^\pi$. Якщо в момент часу $t$ був відвіданий нетермінальний стан $s_t$, то обидва методи оновлять свої наближення $V(s_t)$, базуючись на тому, що відбудеться в наступні моменти часу. Так, метод Монте-Карло чекає моменту, коли стане відомим прибуток, отриманий після відвідання поточного стану, а тоді використовує цей прибуток як наближення для $V(s_t)$. Простий алгоритм Монте-Карло для всіх візитів (every-visit Monte Carlo) виглядає наступним чином:
\begin{equation}
V(s_t) \leftarrow V(s_t) + \alpha\left[R_t - V(s_t)\right],
\end{equation}
де $R_t$ "--- реальний прибуток, отриманий протягом поточного епізоду, починаючи з моменту часу $t$, $\alpha$ "--- сталий параметр величини кроку. Такий алгоритм називатимемо \emph{constant-$\alpha$ MC}.

В той час, як MC-метод чекає до закінчення епізоду, TD-метод повинен чекати лише наступного моменту часу. В момент $t+1$ алгоритм формує наближення на основі отриманої винагороди $r_{t+1}$ та наближення $V(s_{t+1})$. Найпростіший TD-алгоритм, знаний як TD(0), виглядає наступним чином:
\begin{equation}
V(s_t) \leftarrow V(s_t) + \alpha\left[r_{t+1} + \gamma V(s_{t+1}) - V(s_t)\right].
\end{equation}

Раніше вже згадувалося, що
\begin{eqnarray}
V^\pi(s) & = & E_\pi \Bigl\{R_t \Big| s_t = s \Bigr\} \label{MC_target}\\
			& = & E_\pi \Biggl\{\sum_{k=0}^{\infty}\gamma^k r_{t+k+1} \Bigg| s_t = s \Biggr\} \nonumber\\
			& = & E_\pi \left\{r_{t+1} + \gamma\sum_{k=0}^{\infty}\gamma^k r_{t+k+2} \Bigg| s_t = s \right\} \nonumber\\
			& = & E_\pi \left\{r_{t+1} + \gamma V^\pi(s_{t+1}) \bigg| s_t = s \right\}.\label{DP_target}
\end{eqnarray}

Таким чином, з попереднього запису видно, що MC-метод використовує наближення з (\ref{MC_target}) як бажане значення ціннісної функції, а DP-метод "--- з (\ref{DP_target}). Бажане значення для MC є наближенням, оскільки невідоме математичне сподівання. В випадку з DP воно є наближенням не через матсподівання, яке відоме з моделі динаміки середовища, а через те, що саме значення $V^\pi(s_{t+1})$ невідоме. Для TD-методу ми ж отримуємо наближення і через невідомість матсподівання, і через невідомість реального значення $V^\pi(s_{t+1})$. В табл.~\ref{TD0_algorithm} поданий алгоритм TD(0).

\begin{table}
\centering
\label{TD0_algorithm}
\begin{tabular}{|l|}
\hline\\
Ініціалізувати $V(s)$ довільним значенням\\
Ініціалізувати $\pi$ стратегією, яка відповідає згенерованій $V(s)$\\
Для кожного епізоду повторювати:\\
\hspace{0.5cm} Ініціалізувати $s$\\
\hspace{0.5cm} Повторювати для кожного кроку епізоду:\\
\hspace{1cm} 	$a \leftarrow $ дія, пропонована поточною стратегією $\pi$ для стану $s$\\
\hspace{1cm} 	Виконати дію $a$; спостерегти винагороду $r$ та наступний стан $s'$\\
\hspace{1cm} 	$V(s) \leftarrow V(s) + \alpha\left[r + \gamma V(s') - V(s)\right]$\\
\hspace{1cm} 	$s \leftarrow s'$\\
\hspace{0.5cm} поки $s$ "--- нетермінальний стан\\
\\
\hline
\end{tabular}
\caption{Алгоритм TD(0) для наближення $V^\pi$.}
\end{table}

\subsubsection{Sarsa: On-Policy TD Control}

Розглянемо тепер застосування TD-алгоритмів до задачі контролю. Натомість ціннісної функції станів ми будемо намагатися вивчити ціннісну функцію стану-дії $Q^\pi(s,a)$. Нагадаємо, що епізод складається з почергової послідовності станів та пар стан-дія:

\begin{center}\includegraphics[width=0.7\textwidth]{sarsa_diagram.png}\end{center}

Раніше ми розглядали переходи зі стану в стан і вивчення цінності станів. Тепер ми будемо розглядати переходи між парами стан-дія і вивчення цінності стану-дії. Відповідне правило навчання виглядає наступним чином:
\begin{equation}
Q(s_t,a_t) \leftarrow Q(s_t,a_t) + \alpha\left[r_{t+1} + \gamma Q(s_{t+1},a_{t+1}) - Q(s_t, a_t)\right].
\end{equation}

Це оновлення робиться після кожного переходу з нетермінального стану $s_t$. Якщо $s_{t+1}$ "--- термінальний стан, то $Q(s_{t+1}, a_{t+1})$ визначається рівним нулю. Це правило використовує кожен елемент з п'ятірки подій, $(s_t,a_t,r_{t+1},s_{t+1},a_{t+1})$, що становлять перехід з однієї пари стан-дія в іншу. Ця п'ятірка і дала назву алгоритму "--- \emph{Sarsa}.

\begin{table}
\centering
\label{Sarsa_algorithm}
\begin{tabular}{|l|}
\hline\\
Ініціалізувати $Q(s,a)$ довільним чином\\
Для кожного епізоду повторювати:\\
\hspace{0.5cm} Ініціалізувати $s$\\
\hspace{0.5cm} Обрати $a$ зі стану $s$ згідно стратегії, що базується на $Q$ (наприклад, $\varepsilon$-жадібну)\\
\hspace{0.5cm} Повторювати для кожного кроку епізоду:\\
\hspace{1cm} 	Здійснити дію $a$, спостерегти $r$, $s'$\\
\hspace{1cm} 	Обрати $a'$ зі стану $s'$ згідно стратегії\\
\hspace{1cm} 	$Q(s,a) \leftarrow Q(s,a) + \alpha\left[r + \gamma Q(s',a') - Q(s,a)\right]$\\
\hspace{1cm} 	$s \leftarrow s';\ a \leftarrow a';$\\
\hspace{0.5cm} поки $s$ "--- нетермінальний стан\\
\\
\hline
\end{tabular}
\caption{TD-алгоритм контролю Sarsa.}
\end{table}

\subsubsection{Off-Policy Control: Q-Learning}

Однокроковий алгоритм Q-learning:
\begin{equation}
Q(s_t,a_t) \leftarrow Q(s_t,a_t) + \alpha\left[r_{t+1} + \gamma \max_a Q(s_{t+1},a) - Q(s_t,a_t)\right].
\end{equation}

Збігається до $Q^*$ з ймовірністю 1.

\begin{table}
\centering
\label{Q_algorithm}
\begin{tabular}{|l|}
\hline\\
Ініціалізувати $Q(s,a)$ довільним чином\\
Для кожного епізоду повторювати:\\
\hspace{0.5cm} Ініціалізувати $s$\\
\hspace{0.5cm} Повторювати для кожного кроку епізоду:\\
\hspace{1cm} Обрати $a$ зі стану $s$ згідно стратегії, що базується на $Q$ (наприклад, $\varepsilon$-жадібну)\\
\hspace{1cm} 	Здійснити дію $a$, спостерегти $r$, $s'$\\
\hspace{1cm} 	$Q(s,a) \leftarrow Q(s,a) + \alpha\left[r + \gamma \max_{a'}Q(s',a') - Q(s,a)\right]$\\
\hspace{1cm} 	$s \leftarrow s';$\\
\hspace{0.5cm} поки $s$ "--- нетермінальний стан\\
\\
\hline
\end{tabular}
\caption{Q-learning: off-policy TD-алгоритм контролю.}
\end{table}

\subsubsection{Actor-Critic Methods}

\begin{center}\includegraphics[width=0.6\textwidth]{actor_critic_diagram.png}\end{center}
\subsubsection{R-Learning for Undiscounted Continuous Tasks}

\subsection{Eligibility Traces}

\emph{Сліди правомірності (?) (eligibility traces)} "--- це один з базових механізмів навчання з підсиленням. Практично будь-який TD-метод, наприклад, Sarsa або Q-learning, можна об'єднати з eligibity traces для отримання більш загального алгоритму, який би міг навчатися швидше.

\subsubsection{n-крокове TD-прогнозування}

\begin{equation}
\label{n_step_truncated_return}
R_t^{(n)} = r_{t+1} + \gamma r_{t+2} + \gamma^2 r_{t+3} + \cdots + \gamma^{n-1} r_{t+n} + \gamma^n V_t(s_{t+n}).
\end{equation}

Формула (\ref{n_step_truncated_return}) називається \emph{скоректованим n-кроковим обрізаним прибутком (corrected n-step truncated return)} або просто \emph{n-кроковим прибутком}.
Якщо $T-t\leq n$, то $R_t^{(n)} = R_t^{(T-t)}=R_t.$ Тобто останні $n$ n-крокових прибутків "--- це повні дійсні прибутки, як у методах Монте-Карло. Таке визначення дозволяє трактувати прибутки в методах Монте-Карло як особливий випадок нескінченно-крокових прибутків.

\emph{$\lambda$-прибуток} визначається наступним чином:
\begin{equation}
R_t^\lambda = (1-\lambda)\sum_{n=1}^\infty \lambda^{n-1} R_t^{(n)}.
\end{equation}

\begin{figure}
\centering
\includegraphics[width=0.5\textwidth]{td_lambda_backup_diagram.png}
\label{TD_lamda_backup_diagram}
\caption{The backup diagram for TD($\lambda$).}
\end{figure}

\begin{figure}
\centering
\includegraphics[width=0.9\textwidth]{lamda_weighting.png}
\label{lamda_weighting}
\caption{Вага, яка дається кожному з n-крокових прибутків в $\lambda$-прибутку.}
\end{figure}

\includegraphics[width=0.9\textwidth]{eligibility_traces_formula.png}

\includegraphics[width=0.9\textwidth]{eligibility_traces_diagram.png}

\includegraphics[width=0.8\textwidth]{td_lamda_algorithm.png}

\subsubsection{TD($\lambda$)}
\subsubsection{Sarsa($\lambda$)}
\subsubsection{Q($\lambda$)}
\subsubsection{Accumulation vs. Replacing Eligibility Traces}
